// https://leetcode.cn/problems/product-of-array-except-self/description/

// 算法思路总结：
// 1. 前后缀乘积数组解决除自身以外数组的乘积
// 2. 前缀乘积f[i]：nums[0]到nums[i-1]的乘积
// 3. 后缀乘积g[i]：nums[i+1]到nums[m-1]的乘积
// 4. 结果ret[i] = f[i] × g[i]（即前缀积×后缀积）
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int m = nums.size();
        vector<int> f(m, 1), g(m, 1);

        for (int i = 1 ; i < m ; i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }

        for (int i = m - 2 ; i >= 0 ; i--)
        {
            g[i] = g[i + 1] * nums[i + 1];
        }

        vector<int> ret(m);
        for (int i = 0 ; i < m ; i++)
        {
            ret[i] = f[i] * g[i];
        }

        return ret;
    }
};
int main()
{
    vector<int> nums1 = {1,2,3,4}, nums2 = {-1,1,0,-3,3};
    Solution sol;

    auto v1 = sol.productExceptSelf(nums1);
    auto v2 = sol.productExceptSelf(nums2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}